package com.datastructure.practice;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class TotalOfFourNumber {
    public static void main(String[] args) {
        int [] nums = {1,-2,-5,-4,-3,3,3,5};
        Solution3 solution3 = new Solution3();
        System.out.println(solution3.fourSum(nums,-11));
    }
}

class Solution3 {

    public List<List<Integer>> fourSum(int[] nums, int target){
        List<List<Integer>> datas = new ArrayList<>();
        List<List<Integer>> pres;
        int length = nums.length;
        if(nums==null||length<4){
            return datas;
        }
        Arrays.sort(nums);
        int[] pre = new int[nums.length-1];
        int time = 0;
        for(int i = 0; i < length; i++){
            for(int j = 0; j < length; j++){
                if(j!=i){
                    pre[time] = nums[j];
                    time++;
                }
            }
            time = 0;
            pres = threeSum(pre, target - nums[i], nums[i]);
            for (List<Integer> list : pres) {
                Collections.sort(list);
                if(!datas.contains(list)){
                    datas.add(list);
                }
            }
        }
        return datas;
    }

    public List<List<Integer>> threeSum(int[] nums, int target, int interim) {
        List<List<Integer>> data = new ArrayList<>();
        int length = nums.length;
        int sum =0;
        if(nums==null||length<3){
            return data;
        }
        Arrays.sort(nums);
        for(int i = 0;i < length;i++){
            if(nums[i]>target&&target>=0) break;
            if(i > 0 && nums[i]==nums[i-1]) continue;
            int L = i + 1;
            int R = length - 1;
            while (L<R){
                sum = nums[i]+nums[L]+nums[R];
                if(sum==target){
                    data.add(Arrays.asList(nums[i],nums[L],nums[R],interim));
                    while (L<R && nums[L] == nums[L+1]) L++; // 去重
                    while (L<R && nums[R] == nums[R-1]) R--; // 去重
                    L++;
                    R--;
                } else if(sum<target){
                    L++;
                } else if(sum>target){
                    R--;
                }
            }
        }
        return data;
    }
}
